package basic.study.leetcode;

/**
 * @ClassName Mid148
 * @Description 排序链表
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/30 10:51
 * @Version 1.0
 */
public class Mid148 {
    class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }

            ListNode fast = head;
            ListNode slow = head;
            ListNode pre = null;

            while (fast != null && fast.next != null) {
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            pre.next = null;

            ListNode l1 = sortList(head);
            ListNode l2 = sortList(slow);

            return merge(l1, l2);
        }

        private ListNode merge(ListNode l1, ListNode l2) {
            ListNode p = new ListNode(-1);
            ListNode node = p;

            while (l1 != null && l2 != null) {
                if (l1.val > l2.val) {
                    p.next = l2;
                    l2 = l2.next;
                } else {
                    p.next = l1;
                    l1 = l1.next;
                }
                p = p.next;
            }
            if (l1 != null) {
                p.next = l1;
            }
            if (l2 != null) {
                p.next = l2;
            }
            return node.next;
        }
    }

    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}
